package demo9;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-26
 * Time: 10:35
 */
public class testCountSort {
    public static void countSort1(int[] arr) {
        if(arr==null||arr.length<2){
            return;
        }

        //找出数组中的最大值
        int max = arr[0];
        int min = arr[0];
        for(int i =0;i<arr.length;++i){
            max = Math.max(max,arr[i]);
            min = Math.min(min,arr[i]);
        }
        //利用数组记录每个元素在对应下标出现的个数
        int[] hash = new int[max - min +1];
        for(int i =0;i<arr.length;++i){
            hash[arr[i]]++;
        }
        int i=0;
        for(int j =0;j<hash.length;++j){
            while(hash[j]-- >0){
                arr[i++] = j;
            }
        }

    }

    public static void main(String[] args) {
        int[] arr = {27 ,42, 37, 135, 148, 148 ,97, 80, 148, 129,
                50, 68, 9, 26, 142, 1, 71, 75, 69, 48 ,57, 144, 132, 27, 0, 25, 31 };
        System.out.println(Arrays.toString(arr));
        countSort1(arr);
        System.out.println(Arrays.toString(arr));
    }


}
